package com.dyz.leetcode._15_BFSAndDFS;

import java.util.ArrayDeque;
import java.util.Queue;

public class _463_islandPerimeter {
    //上下左右方向
    private int[][] dirs = {{-1, 0},{1, 0},{0, -1},{0, 1}}; //左边 右边 上边 下边
    //数组
    private int[][] grid;
    //行
    private int rows;
    //列
    private int cols;
    private boolean[][] visited;
    private int res =0;
    //深度优先遍历
    public int islandPerimeter(int[][] grid){
        this.grid = grid;
        this.rows = grid.length;
        this.cols = grid[0].length;
        this.visited = new boolean[rows][cols];

        for(int row=0; row<rows; row++){
            for(int col=0; col<cols; col++){
                if(grid[row][col]==1){
                    dfs(row, col);
                    return res;
                }
            }
        }
        return 0;

    }

    private void dfs(int row, int col){
        if(!isArea(row, col) || grid[row][col]==0||visited[row][col]){
            return;
        }

        visited[row][col] = true;
        //该row与col下四个方向
        for(int[] dir:dirs){
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];
            if(!isArea(nextRow, nextCol) || grid[nextRow][nextCol]==0){
                res++;
            }
            dfs(nextRow, nextCol);
        }

    }

    private boolean isArea(int row, int col){
        return row >= 0 && row < rows && col >= 0 && col < cols;
    }


    //2. 后序遍历
    public int islandPerimeter1(int[][] grid){
        this.grid = grid;
        this.rows = grid.length;
        this.cols = grid[0].length;
        this.visited = new boolean[rows][cols];

        for(int row=0; row<rows; row++){
            for(int col=0; col<cols; col++){
                if(grid[row][col]==1){
                    return dfs1(row, col);
                }
            }
        }
        return 0;
    }

    private int dfs1(int row, int col){
        if(!isArea(row, col) || grid[row][col]==0){return 1;}
        if(visited[row][col]){return 0;}

        visited[row][col] = true;
        int res = 0;
        for(int[] dir:dirs){
            int nextRow = row+dir[0];
            int nextCol = col+dir[1];
            res+=dfs1(nextRow, nextCol);
        }
        return res;
    }
    //BFS
    public int islandPerimeter2(int[][] grid){
        this.grid = grid;
        this.rows = grid.length;
        this.cols = grid[0].length;
        this.visited = new boolean[rows][cols];

        for(int row=0; row<rows; row++){
            for(int col=0; col<cols; col++){
                if(grid[row][col]==1){
                    return bfs(row, col);
                }
            }
        }
        return 0;

    }

    private int bfs(int row, int col){
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{row, col});
        visited[row][col] = true;
        int res = 0;
        while (!queue.isEmpty()){
            int[] curr = queue.poll();
            for(int[] dir:dirs){
                int nextRow = curr[0]+dir[0];
                int nextCol = curr[1]+dir[1];
                if(!isArea(nextRow, nextCol) || grid[nextRow][nextCol]==0){
                    res+=1;
                }else if(!visited[nextRow][nextCol]){
                    queue.offer(new int[]{nextRow, nextCol});
                    visited[nextRow][nextCol]=true;
                }
            }
        }
        return res;
    }
}
